◀ Prev · Parts · Full · Next ▶

where f(y) is the value/cost of the solution y for the instance x. Clearly, the performance guarantee is greater than or equal to 1 and equal to 1 if and only if y is an optimal solution. If an algorithm A guarantees to return solutions with a performance guarantee of at most r(n), then A is said to be an r(n)-approximation algorithm and has an approximation ratio of r(n). Likewise, a problem with an r(n)-approximation algorithm is said to be r(n)-approximable or have an approximation ratio of r(n).cite-ref-ausiello99complexity-12-0[12]cite-ref-kann92onthe-13-0[13]

For minimization problems, the two different guarantees provide the same result and that for maximization problems, a relative performance guarantee of ρ is equivalent to a performance guarantee of r = ρ ρ − − 1 {\displaystyle r=\rho ^{-1}} . In the literature, both definitions are common but it is clear which definition is used since, for maximization problems, as ρ ≤ 1 while r ≥ 1.

The absolute performance guarantee P A {\displaystyle \mathrm {P} _{A}} of some approximation algorithm A, where x refers to an instance of a problem, and where R A ( x ) {\displaystyle R_{A}(x)} is the performance guarantee of A on x (i.e. ρ for problem instance x) is:

P A = inf { r ≥ ≥ 1 ∣ ∣ R A ( x ) ≤ ≤ r , ∀ ∀ x } . {\displaystyle \mathrm {P} _{A}=\inf\{r\geq 1\mid R_{A}(x)\leq r,\forall x\}.}

That is to say that P A {\displaystyle \mathrm {P} _{A}} is the largest bound on the approximation ratio, r, that one sees over all possible instances of the problem. Likewise, the asymptotic performance ratio R A ∞ ∞ {\displaystyle R_{A}^{\infty }} is:

◀ Prev · Parts · Full · Next ▶